package leetcode101.tree;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @author Synhard
 * @version 1.0
 * @class Code6
 * @description 1110. 删点成林
 * 给出二叉树的根节点 root，树上每个节点都有一个不同的值。
 *
 * 如果节点值在 to_delete 中出现，我们就把该节点从树上删去，最后得到一个森林（一些不相交的树构成的集合）。
 *
 * 返回森林中的每棵树。你可以按任意顺序组织答案。
 *
 *
 *
 * 示例：
 *
 * 输入：root = [1,2,3,4,5,6,7], to_delete = [3,5]
 * 输出：[[1,2,null,4],[6],[7]]
 *
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-06-22 9:13
 */
public class Code6 {



    public static void main(String[] args) {

    }

    public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
        List<TreeNode> res = new ArrayList<>();
        Set<Integer> set = new HashSet<>();
        for (int i : to_delete) {
            set.add(i);
        }
        dfs(root, true, set, res);
        return res;
    }

    private TreeNode dfs(TreeNode root, boolean isRoot, Set<Integer> set, List<TreeNode> res) {
        if (root == null) {
            return null;
        }
        boolean isDel = set.contains(root.val);
        if (!isDel && isRoot) {
            res.add(root);
        }
        root.left = dfs(root.left, isDel, set, res);
        root.right = dfs(root.right, isDel, set, res);
        return isDel ? null : root;
    }

}
/*
由于每一个结点都可能被删除，所以需要遍历整棵树
使用根-左-右的方式进行遍历
返回结果是当前结点或者null
如果当前结点属于根节点并且不被删除，则加入结果中
每次函数对当前结点进行判断和处理，判断其是否需要加入结果中，是否需要被删除
 */